package dfs_bfs;

/**
 * 当确定某一个元素没能覆盖的时候需要将此岛全部置零
 */
public class lc1905 {
    public static void main(String[] args) {
        System.out.println(countSubIslands(new int[][]{{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}},
                new int[][]{{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}}));
        System.out.println(countSubIslands(new int[][]{{1,0,1,0,1},{1,1,1,1,1},{0,0,0,0,0},{1,1,1,1,1},{1,0,1,0,1}},
                new int[][]{{0,0,0,0,0},{1,1,1,1,1},{0,1,0,1,0},{0,1,0,1,0},{1,0,0,0,1}}));
    }
    static int t = 1;
    public static int countSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid1.length;
        int n = grid1[0].length;
        int re = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid2[i][j] == 1){
                    t = 1;
                    dfs(grid1, grid2, i, j);
                        re += t;
                }
            }
        }
        return re;
    }
    public static void dfs(int[][] grid1 ,int[][] grid2, int i, int j){
        if(i < 0 || j < 0 || i >= grid1.length || j >= grid1[0].length || grid2[i][j] == 0)
            return;
        if(grid1[i][j] != 1)
            t = 0;
        grid2[i][j] = 0;
        dfs(grid1, grid2, i + 1, j);
        dfs(grid1, grid2, i - 1, j);
        dfs(grid1, grid2, i, j + 1);
        dfs(grid1, grid2, i, j - 1);
    }

}
/*
System.out.println(countSubIslands(new int[][]{{1,0,1,0,1},{1,1,1,1,1},{0,0,0,0,0},{1,1,1,1,1},{1,0,1,0,1}},
                new int[][]{{0,0,0,0,0},{1,1,1,1,1},{0,1,0,1,0},{0,1,0,1,0},{1,0,0,0,1}}));
 */